package com.yt.ds.chapter2.exercise;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: lzf
 * @Date: 2020/7/13 16:59
 * @Description:
 */
public class Exercise2_2_14 {
    public static void main(String[] args) {
        Queue<Comparable> queue1 = new LinkedList<>();
        queue1.add(1);
        queue1.add(3);
        queue1.add(5);
        queue1.add(7);
        queue1.add(8);

        Queue<Comparable> queue2 = new LinkedList<>();
        queue2.add(2);
        queue2.add(4);
        queue2.add(6);
        queue2.add(9);

        Queue<Comparable> mergedQueue = mergeQueues(queue1, queue2);

        for (Comparable item : mergedQueue) {
            System.out.println(item + " ");
        }
        System.out.println("\nExpected: 1 2 3 4 5 6 7 8 9");
    }

    private static Queue<Comparable> mergeQueues(Queue<Comparable> queue1, Queue<Comparable> queue2) {
        Queue<Comparable> queue = new LinkedList<>();

        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            Comparable value1 = queue1.peek();
            Comparable value2 = queue2.peek();
            if (value1 == null) {
                queue.add(queue2.poll());
            } else if (value2 == null) {
                queue.add(queue1.poll());
            } else if (value1.compareTo(value2) < 0) {
                queue.add(queue1.poll());
            } else {
                queue.add(queue2.poll());
            }
        }
        return queue;
    }
}
